package com.test.daily.leetcode.y2022.m06.day0609.v02;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/6/9 下午 02:10
 * @version: 1.0
 */
public class Solution {

    public  int longCommon(String s1, String s2) {
        if (s1 == null || s1.length() == 0 || s2 == null || s2.length() == 0) {
            return 0;
        }
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int i = str1.length;
        int j = str2.length;
        return process1(str1, str2, i, j);

    }

    public  int process1(char[] s1, char[] s2, int i, int j) {
        if(i == 0 && j == 0){
            return s1[i] == s2[j] ? 1: 0;
        } else if(i == 0){
            if(s1[i] == s2[j]){
                return 1;
            } else {
                return process1(s1, s2, i, j-1);
            }
        }else if(j == 0){
            if(s1[i] == s2[j]){
                return 1;
            } else {
                return process1(s1, s2, i-1, j);
            }
        } else {
            int p1 = process1(s1, s2, i-1, j);
            int p2 = process1(s1, s2, i, j -1);
            int p3 = s1[i] == s2[j] ? 1 + process1(s1, s2, i-1, j-1): 0;
            int ans = Math.max(p1, Math.max(p2, p3));
            return ans;
        }
    }

    public  int longCommon2(String s1, String s2){
        if(s1 == null || s1.length() == 0 || s2 == null || s2.length() == 0 ){
            return 0;
        }
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int M = str1.length;
        int N = str2.length;
        int[][] dp = new int[M][N];
        for(int i = 0; i < M; i++){
            for(int j = 0; j < N; j++){
                dp[i][j] = -1;
            }
        }

        return process2(str1, str2, M-1, N-1,dp);
        // return process2(str1, str2, i, j)
    }

    public  int process2(char[] str1, char[] str2, int i, int j, int[][] dp){

        if(dp[i][j] != -1){
            return dp[i][j];
        }
        int ans = -1;
        if(i == 0 && j == 0){
           ans = str1[i] == str2[j] ? 1 : 0;
        } else if(i == 0){
            if(str1[i] == str2[j]){
                ans = 1;
            } else {
                ans = process2(str1, str2, i, j-1, dp);
            }
        } else if(j == 0){
            if(str1[i] == str2[j]){
                ans = 1;
            } else {
                ans = process2(str1, str2, i-1, j, dp);
            }
        }else{
            int p1 = process2(str1, str2, i, j-1,dp);
            int p2 = process2(str1, str2, i-1, j, dp);
            int p3 = str1[i] == str2[j] ? (1 + process2(str1, str2, i-1, j-1, dp)): 0;
            ans = Math.max(p1, Math.max(p2, p3));
        }
        dp[i][j] = ans;
        return ans;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.longCommon3("abcde", "ace"));
    }

    public int longCommon3(String text1, String text2){
        char[] str1 = text1.toCharArray();
        char[] str2 = text2.toCharArray();
        int M = str1.length;
        int N = str2.length;
        int[][] dp = new int[M][N];
        dp[0][0] = str1[0] == str2[0] ? 1 : 0;
        for(int i = 1; i < M; i++){
            dp[i][0] = str1[i] == str2[0] ? 1 : dp[i-1][0];
        }
        for(int j = 1; j < N; j++){
            dp[0][j] = str1[0] == str2[j] ? 1: dp[0][j-1]; 
        }
        for(int i = 1; i < M; i++){
            for(int j = 1; j < N; j++){
                int p1 = dp[i][j-1];
                int p2 = dp[i-1][j];
                int p3 = str1[i] == str2[j] ? (1 + dp[i-1][j-1]): 0;
                dp[i][j] = Math.max(p1, Math.max(p2, p3));
            }
        }
        return dp[M-1][N-1];
    }
}
